/*
 * d_list.c
 * Asif Shahidullah
 *
 * Contains the doubly-linked list implementation, along with
 * several static functions which are necessary for its
 * operation.
 *
 * Note: this is a fully implemented doubly-linked list - despite
 * the fact that it was not required for this project. Some
 * functions are not called at all because they are unnecessary.
 */

#include <stdio.h>
#include <stdlib.h>

#include "list_data.h"
#include "d_list.h"

/* Create a node object */
static __inline__ Node create_node (LData);

/* Free a node object */
static __inline__ void dealloc_node (Node);

/* Get the node at an index - NOT INDEX SAFE */
static __inline__ Node get_node (Node, int);

/* This function is not necessary at all when compling with gcc
 * 4.7.2, since it initializes all variables on creation. It is
 * required for 4.0.3, the version codon employs ... */
List allocate_list () {
	List list;

	if ((list = (List) malloc (sizeof (struct list_t))) == NULL) {
		fprintf (stderr, "Failed to allocate memory for List.\n");
		return NULL;
	}

	list->size = 0;
	list->head = NULL;
	list->tail = NULL;

	return list;
}

int init_list (List list, LData data) {
	Node first_node;

	/* Make sure we aren't reinitializing a list */
	if (list->size > 0) {
		fprintf (stderr, "Attempted initilization of initialized list, "
			"inserting as head instead.\n");
    return insert_node (list, 0, data);
  }

	/* Create Node */
  if ((first_node = create_node (data)) != NULL) {
		first_node->prev = NULL;
		first_node->next = NULL;
		list->head = first_node;
		list->tail = first_node;
		list->size = 1;
	} else {
		fprintf (stderr, "List head creation failure.\n");
		return 0;
	}

	return 1;
}


int get_index (List list, LData data) {
	Node temp;
	int index;

	if (list->size < 1)
		return -1;

	temp = list->head;
	for (index = 0; index < list->size; index++)
		if (is_LData_match (data, temp->data))
			return index;

	return -1;
}


LData get (List list, int index) {
	Node node;
	int c_index;

	if (index < 0 || index >= list->size) {
		fprintf (stderr, "Attempted fetch of nonexistant index.\n");
		return NULL;
	}

	node = list->head;
	for (c_index = 0; c_index != index; c_index++)
		node = node->next;

	return node->data;
}


int insert_node (List list, int index, LData data) {
	Node insert, obsolete;

	if (index < 0 || index > list->size) {
		fprintf (stderr, "Attempted insert into nonexistant index.\n");
		return 0;
	}

	if ((insert = create_node (data)) == NULL) {
		fprintf (stderr, "Failed to create node for insertion into "
			"index: %d.\n", index);
		return 0;
	}

	if (list->size == 0)
		return init_list(list, data);
	
	obsolete = get_node (list->head, index);

	/* Insert a new head */
	if (index == 0) {
		insert->next = obsolete;
		insert->prev = NULL;
		if (obsolete != NULL)
			obsolete->prev = insert;
		list->head = insert;
	} 

	/* Insert a new tail */
	else if (index == list->size) {
		insert->next = NULL;
		insert->prev = list->tail;
		if (list->tail != NULL)
			list->tail->next = insert;
		list->tail = insert;
	} 

	/* Regular insert */
	else {
		insert->next = obsolete;
		obsolete->prev->next = insert;
		insert->prev = obsolete->prev;
		obsolete->prev = insert;
	}

	list->size++;
	return 1;	
}


LData remove_node (List list, int index) {
	Node remove;
	LData data;
	
	if (index < 0 || index >= list->size) {
		fprintf (stderr, "Attempted removal of nonexistant index.\n");
		return 0;	
	}

	remove = get_node (list->head, index);

	/* Remove the head */
	if (index == 0) {
		list->head = list->head->next;
	} 

	/* Remove the tail */
	else if (index == (list->size - 1)) {
		list->tail = list->tail->prev;
	}

	/* Regular remove a node */
	else {
		remove->prev->next = remove->next;
		remove->next->prev = remove->prev;
	}
	
	data = remove->data;
	dealloc_node (remove);	

	list->size--;
	return data;
}

void deinit_list (List list) {
	/* Special case of empty list */
	if (list->size == 0) {
		fprintf (stderr, "Attempted deinitialization of empty list.\n");
		return;
	}

	while (list->size > 0)
		dealloc_LData (remove_node (list, 0));
	
	free (list);
	return;
}

/*****************  STATIC FUNCTIONS - INTERNAL USE ONLY *****************/ 
Node create_node (LData data) {
	Node temp = NULL;
	if ((temp = (Node) malloc (sizeof (struct list_element_t))))
		temp->data = data;
	else
		fprintf (stderr, "Node allocation failure.\n");
	return temp;
}

void dealloc_node (Node node) {
	free (node);
}

Node get_node (Node current, int index) {
	int i;
	for (i = 0; i != index; i++)
		current = current->next;
	return current;
}
